Link
大概就是给你一段序列，然后让你对一些数做出一些调整，最后使得这个序列单调不升或者单调不减。显然是一个动态规划问题，而较为显然的是对于每一个数，要么不修改，要么就是修改成原来序列中的某一个数的值。
至于为什么，大家可以手推几组数据，或者说来看一下一个错误的贪心法。对于每一个数我们将它修改成相邻两个数中的差值最小的一个，然后就可以保证单调性。但是这样显然是不对的，因为它具有单调性，自己改变之后后面一个数修改的情况有可能也会发生改变。但是我们依然可以知道：数的修改一定存在于当前序列的数中这一点是没错的。
因此首先我们进行排序，那么原序列$A$最终肯定要变成这个排完序之后的序列$B$，于是我们就有了$DP$的思路。
设$Dp[i][j]$表示第$i$个数修改成$j$的最小花费，然后就有
加个单调队列就可以$O(N^2)$过了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std ;
typedef long long LL ;
const int MAXN = 2010 ;
const int MAXM = 2010 ;
const int INF = 1e9 ;
int N, Tall[MAXN], Old[MAXN], Dp[MAXN][MAXN], Q[MAXN], Ans = INF, T ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
int main() {
N = Read() ;
for (int i = 1 ; i <= N ; i ++)
Tall[i] = Read(), Old[i] = Tall[i] ;
sort(Old + 1, Old + N + 1) ;
for (int i = 1 ; i <= N ; i ++) {
T = 0 ;
for (int j = 1 ; j <= N ; j ++) {
while (T && Dp[i - 1][j] < Dp[i - 1][Q[T]]) T -- ;
Q[++ T] = j ;
Dp[i][j] = Dp[i - 1][Q[1]] + abs(Tall[i] - Old[j]) ;
}
}
for (int i = 1 ; i <= N ; i ++) Ans = min(Ans, Dp[N][i]) ;
memset(Dp, 0, sizeof (Dp)) ;
for (int i = 1 ; i <= N ; i ++){
T = 0 ;
for (int j = N ; j >= 1 ; j --) {
while (T && Dp[i - 1][j] < Dp[i - 1][Q[T]]) T -- ;
Q[++ T] = j ;
Dp[i][j] = Dp[i - 1][Q[1]] + abs(Tall[i] - Old[j]) ;
}
}
for (int i = 1 ; i <= N ; i ++) Ans = min(Ans, Dp[N][i]) ;
printf("%d", Ans) ;
return 0 ;
}